import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {

    public static void main(String[] args) {
        GenerateParenthesis generateParenthesis = new GenerateParenthesis();
        System.out.println(generateParenthesis.generateParenthesis(3));
    }

    List<String> ans = new ArrayList<>();
    StringBuilder str = new StringBuilder();
    public List<String> generateParenthesis(int n) {
        process(n, n, n);
        return ans;
    }

    public void process(int l, int r, int n) {
        if (l == 0 && r == 0) {
            ans.add(str.toString());
            return;
        }


        if (l > 0 && r != 0) {
            str.append("(");
            process(l - 1, r, n);
            str.deleteCharAt(str.length() - 1);
        }
        if (r > 0 && l != n && !(l == r)) {
            str.append(")");
            process(l, r - 1, n);
            str.deleteCharAt(str.length() - 1);
        }

    }
}
